// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_
#define UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_

#include <stdint.h>

#include "base/logging.h"

namespace ui {

// Port of BitSet32 from Android
// * platform/system/core/include/utils/BitSet.h
// * Change-Id: 02c9460a0a05f27e0501f9e64cdf24091e7d3579
// * Please update the Change-Id as upstream Android changes are pulled.
struct BitSet32 {
    uint32_t value;

    inline BitSet32()
        : value(0)
    {
    }
    explicit inline BitSet32(uint32_t value)
        : value(value)
    {
    }

    // Gets the value associated with a particular bit index.
    static inline uint32_t value_for_bit(uint32_t n)
    {
        DCHECK_LE(n, 31U);
        return 0x80000000 >> n;
    }

    // Clears the bit set.
    inline void clear() { value = 0; }

    // Returns the number of marked bits in the set.
    inline uint32_t count() const { return popcnt(value); }

    // Returns true if the bit set does not contain any marked bits.
    inline bool is_empty() const { return !value; }

    // Returns true if the bit set does not contain any unmarked bits.
    inline bool is_full() const { return value == 0xffffffff; }

    // Returns true if the specified bit is marked.
    inline bool has_bit(uint32_t n) const
    {
        return (value & value_for_bit(n)) != 0;
    }

    // Marks the specified bit.
    inline void mark_bit(uint32_t n) { value |= value_for_bit(n); }

    // Clears the specified bit.
    inline void clear_bit(uint32_t n) { value &= ~value_for_bit(n); }

    // Finds the first marked bit in the set.
    // Result is undefined if all bits are unmarked.
    inline uint32_t first_marked_bit() const { return clz(value); }

    // Finds the first unmarked bit in the set.
    // Result is undefined if all bits are marked.
    inline uint32_t first_unmarked_bit() const { return clz(~value); }

    // Finds the last marked bit in the set.
    // Result is undefined if all bits are unmarked.
    inline uint32_t last_marked_bit() const { return 31 - ctz(value); }

    // Finds the first marked bit in the set and clears it.  Returns the bit
    // index.
    // Result is undefined if all bits are unmarked.
    inline uint32_t clear_first_marked_bit()
    {
        uint32_t n = first_marked_bit();
        clear_bit(n);
        return n;
    }

    // Finds the first unmarked bit in the set and marks it.  Returns the bit
    // index.
    // Result is undefined if all bits are marked.
    inline uint32_t mark_first_unmarked_bit()
    {
        uint32_t n = first_unmarked_bit();
        mark_bit(n);
        return n;
    }

    // Finds the last marked bit in the set and clears it.  Returns the bit index.
    // Result is undefined if all bits are unmarked.
    inline uint32_t clear_last_marked_bit()
    {
        uint32_t n = last_marked_bit();
        clear_bit(n);
        return n;
    }

    // Gets the index of the specified bit in the set, which is the number of
    // marked bits that appear before the specified bit.
    inline uint32_t get_index_of_bit(uint32_t n) const
    {
        DCHECK_LE(n, 31U);
        return popcnt(value & ~(0xffffffffUL >> n));
    }

    inline bool operator==(const BitSet32& other) const
    {
        return value == other.value;
    }
    inline bool operator!=(const BitSet32& other) const
    {
        return value != other.value;
    }
    inline BitSet32 operator&(const BitSet32& other) const
    {
        return BitSet32(value & other.value);
    }
    inline BitSet32& operator&=(const BitSet32& other)
    {
        value &= other.value;
        return *this;
    }
    inline BitSet32 operator|(const BitSet32& other) const
    {
        return BitSet32(value | other.value);
    }
    inline BitSet32& operator|=(const BitSet32& other)
    {
        value |= other.value;
        return *this;
    }

private:
#if defined(COMPILER_GCC) || defined(__clang__)
    static inline uint32_t popcnt(uint32_t v)
    {
        return __builtin_popcountl(v);
    }
    // We use these helpers as the signature of __builtin_c{l,t}z has
    // "unsigned int" for the input, which is only guaranteed to be 16b, not 32.
    // The compiler should optimize this away.
    static inline uint32_t clz(uint32_t v)
    {
        if (sizeof(unsigned int) == sizeof(uint32_t)) {
            return __builtin_clz(v);
        } else {
            return __builtin_clzl(v);
        }
    }
    static inline uint32_t ctz(uint32_t v)
    {
        if (sizeof(unsigned int) == sizeof(uint32_t)) {
            return __builtin_ctz(v);
        } else {
            return __builtin_ctzl(v);
        }
    }
#else
    // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    static inline uint32_t popcnt(uint32_t v)
    {
        v = v - ((v >> 1) & 0x55555555);
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        return (((v + (v >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }
    // TODO(jdduke): Use intrinsics (BitScan{Forward,Reverse}) with MSVC.
    static inline uint32_t clz(uint32_t v)
    {
        v |= (v >> 1);
        v |= (v >> 2);
        v |= (v >> 4);
        v |= (v >> 8);
        v |= (v >> 16);
        return 32 - popcnt(v);
    }
    static inline uint32_t ctz(uint32_t v)
    {
        return popcnt((v & static_cast<uint32_t>(-static_cast<int>(v))) - 1);
    }
#endif
};

} // namespace ui

#endif // UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_
